
\section{SALADS Overview}
To illustrate how exactly SALADS randomizes the data structure
memory layout, we use a simple program shown in Figure 2(a) as our
working example. According to the source code, the program has a
data structure \texttt{TEST} with five fields (line 1-7). In
function \texttt{main}, it contains two data structure instances:
\texttt{p} and \texttt{q} (line 11-13), and each of them has one
data structure operation (line 14-15). %SALADS is designed and
%implemented in the gimple phase during gcc compilation.
To get a clear picture of how we transform the code, we also list
the gimple statements produced by the original gcc-4.6.0 in Figure
2(b) and SALADS in Figure 2(c) respectively.


When SALADS compiles the source code, it takes the following steps:
first SALADS parses the source code to track the definition of data
structure (\texttt{TEST} in our example) including the name of the
data structure, original size and offset of each field. Then SALADS
inserts the \emph{randomization record} as well as its manipulation
routines \texttt{Initialize\_Field}(line 17, line 24 in Figure 2
(c)), \texttt{Update\_Record} (line 19, line 26),
\texttt{Offset\_Diff} (line 20, line 27) into the program. The
\emph{randomization record} is a piece of metadata inserted by
SALADS for each data structure instance. Each \emph{randomization
record} contains information about the fields of the data structure
(e.g., size, offset) and runtime status of the data structure
instance (e.g., its address and current randomization seed value).
Next, SALADS iterates the source code to recognize the data
structure operations: \texttt{p-$>$a=1} and \texttt{$q.c$='a'}.
Further SALADS analyzes the operations by extracting the data
structure instances (\texttt{p} and \texttt{q}) as well as the
fields (\texttt{a} and \texttt{c}). For each instance, SALADS uses
\texttt{Initialize\_Field} to fill out the field information
(e.g.,size and offset) into the \emph{randomization record}, and
then it uses the routine \texttt{Update\_Record} to update the
runtime status of the data structure instance (e.g.,address,
randomization seed) in \emph{randomization record} and reorder the
fields in data structure. With the randomized instance, SALADS
calculates the randomized memory address of the field by
\texttt{Offset\_Diff} and replaces the original data structure
operation to access the randomized field. Take \texttt{p-$>$a=1} in
Figure 2 (c) for example, the statements (line 17-23) are used to
access the randomized fields. More specifically,
\texttt{Initialize\_Field}($d$) (line 17) is used to fill out the
field size with $<$4,1,1,4,4$>$ and field offset with
$<$0,4,5,8,12$>$. The parameter $d$ represents the $d$-$th$ data
structure (\texttt{TEST} in our case).
\texttt{Update\_Record}($d$,$addr$) routine (line 19) is used to
update the seed of the instance, and reorder the fields based on the
seed. The parameter $addr$ represents the instance address
(\texttt{p} in our case). Then SALADS uses
\texttt{Offset\_Diff}($d$, $f_i$) routine (line 20) to compute the
difference between randomized offset and original offset and the
result is D.2057, where the parameter $f_i$ represents the $i$-$th$
field for the $d$-$th$ data structure (\texttt{a} in our case). With
the offset difference, SALADS replaces the original data structure
operation using the randomized offset (line 21-23). Similarly, the
statements in line 24-30 achieve the same functions for
\texttt{$q.c$='a'}. Since the seed is randomly selected in the
\texttt{Update\_Record}, instance \texttt{p} and \texttt{q} will get
different memory layout.



\begin{figure*}[t]
\label{overview} \centering
\includegraphics[scale=0.7]{Overview.eps}
\caption{SALADS system overview} \label{fig:overview}
\end{figure*}


Figure~\ref{fig:overview} shows an overview of SALADS system. There
are four key components: \emph{extraction component}, \emph{alias
analysis component}, \emph{normalization component} and
\emph{randomization component}. \emph{Extraction component} is
designed in the abstract syntax tree pass (AST-Pass) and is used to
collect the necessary information for the rest components, including
the data structure definition as well as the external \& shared API
(e.g., GNU C library functions and system calls). Next, SALADS steps
into the \emph{alias analysis component}, which computes all the
points-to information for the data structure instance. With the
collected data structure information and pointer alias information,
SALADS steps into the \emph{normalization component}, it passes
through the source code to find the calculated field offset and the
field referenced by the pointer, further at runtime, it checks the
pointer arithmetic operations that access the field without the
pointer to the entry of the data structure. With the
\emph{normalization component}, SALADS marks all the fields that can
not be randomized, we assume the rest data structure fields can be
randomized. With the results of the previous three components,
including \emph{External \& Shared API}, \emph{Data Structure
Component}, \emph{Normalized Data Structure} and \emph{Data
Structure Points-to Info}, we step into the final component
\emph{randomization component}: Pass-3 \emph{Data Structure Layout
Randomization}, Pass-4 \emph{Data Structure Layout De-randomization}
and Pass-5 \emph{Data Structure Layout Re-randomization}. Pass-3
generates the \emph{randomization record}, which will be updated in
Pass-3 to dynamically change the layout of the data structure
instance. Meanwhile, Pass-3 reorders the fields of the data
structure instance based on the randomization seed. To ensure the
consistency and accuracy of the running program, Pass-4 restores the
default layout of data structures at the \emph{de-randomization
point}. A \emph{de-randomization point} is the execution context at
which a data structure instance should be restored to its original
layout -- for example, when the data structure instance is involved
in an API that interfaces with ``external" code not belonging to the
executable being generated. With the points-to information that is
generated by \emph{Alias Analysis Component}, Pass-5 re-randomizes
the data structure instance that is set as non-randomizable by
Pass-4 if there is no pointer to the data structure instance at the
\emph{re-randomization point}.



\begin{figure*}[t]
\centering
\includegraphics[scale=0.6]{Example3.eps}
\caption{An Example Showing How SALADS Works} \label{fig:example}
\end{figure*}
